package erfen.base;

import java.util.Arrays;

/**
 * 旋转有序数组（如 [4,5,6,7,0,1,2]）中查找目标值
 * 也就是一半一半有序
 */
public class RotatedArraySearch {

    public static int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;

        while (left <= right) {
            int mid = (left+right)>>>1;
            if (nums[mid] == target) {
                return mid; // 直接找到目标值
            }
            // 判断左半部分是否有序
            if (nums[left] <= nums[mid]) {
                // 目标值在有序左半部分的范围内
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            // 否则右半部分有序
            else {
                // 目标值在有序右半部分的范围内
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1; // 未找到
    }

    public static void main(String[] args) {
        // 测试用例
        int[] nums1 = {4, 5, 6, 7, 0, 1, 2};
        testCase(nums1, 0,4); // 输出: 4
        testCase(nums1, 3,-1); // 输出: -1

        int[] nums2 = {1, 3};
        testCase(nums2, 3,1); // 输出: 1
    }

    private static void testCase(int[] nums, int target, int expected) {
        int result = search(nums, target);
        System.out.printf("数组: %s, 目标: %d => 结果: %d (预期: %d) %s\n",
                Arrays.toString(nums), target, result, expected,
                result == expected ? "✓" : "✗");
    }
}